Shor's algorithm
https://en.wikipedia.org/wiki/Shor%27s_algorithm "Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm (an algorithm that runs on a quantum computer) for integer factorization formulated in 1994. Informally, it solves the following problem: given an integer N, find its prime factors." Background The most resilient proof of any proposed quantum computer is to out-perform conventional computers at some task where there is known to be a quantum speedup. The first task of this sort discovered was summarised in a 1985 paper by David Deutsch through the creation of a theoretical "black box problem" that was specifically designed to show that quantum superposition allows measurements to be made on multiple observables of a system simultaneously, and hence for certain tasks the total number of measurements can be reduced significantly. This was later presented in a generalised form as the "Deutsch-Josza algorithm" which now solved this specific 'black box problem' exponentially faster than manual measurements by using quantum superposition and entanglement. Analogy The algorithms can be simplified in an analogy to a light switch. The first algorithm involved an experiment in which a light is shone a certain number of times between 0 and 2. The target of the light is a 'black box' which may respond differently to being shone by no light (00), shone by two pulses of light (11) and also depending on the timing of single pulses (responds differently to 10 and 01). We are told that either: a) the black box gives the same response regardless of the pulsing; or b) the box gives as many positive reactions (lights up) as negative reactions (stays black). The key to understanding the algorithm is to realise that under the logic of classical physics it is impossible to know whether the black box is of type "a)" or "b)" until you have measured ... finsih later https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm http://www.cs.xu.edu/~kinne/quantum/deutche.html https://en.wikipedia.org/wiki/Grover%27s_algorithm Summary , in which large prime numbers are known to have been multiplied to produce a particularly large number. Verification of this simple multiplication is memory-intensive (since the numbers are so large) but computationally simple. However, searching for such primes is both memory-intensive and computationally intractable (meaning if you build a computer that can solve it for an N-digit number in T seconds, then having it solve it for an (N2)-digit number takes much, much longer than T2 seconds). Quantum computers are known to be much more efficient at solving Shor's algorithm, since regardless of the size of the number, the process of finding prime factors is not based on merely consecutively searching through possible factors, but rather about searching for the coherent frequencies which correspond to its prime factors. Simply put, the algorithm transforms the problem of 'prime factorization' into a problem of finding a harmonic frequency (f) and the wave-number (N) that allow those primes to multiply to give the composite number. If the number is 1,220,125,289 (1 billion, 220 million, 125 thousand, 289) and we know that there are just two solitary factors, it isn't simple to create a process to figure out these factors much quicker than searching through all of them (see Prime Factors#Complex Harmonics). However, quantum computers are able to use superposition to amplify the resonance of the underlying prime harmonics to probabilisitically improve the chances of finding the prime factor in times that scales polynomially with log(N), as opposed to scaling with N (which is much larger than log(N) for large N). Wikipedia https://en.wikipedia.org/wiki/Shor%27s_algorithm#Explanation_of_the_algorithm "The algorithm is composed of two parts. The first part of the algorithm turns the factoring problem into the problem of finding the period of a function, and may be implemented classically. The second part finds the period using the quantum Fourier transform, and is responsible for the quantum speedup." "Shor's period-finding algorithm relies heavily on the ability of a quantum computer to be in many states simultaneously. Physicists call this behavior a "superposition" of states. To compute the period of a function f'', we evaluate the function at all points simultaneously. Quantum physics does not allow us to access all this information directly, though. A measurement will yield only one of all possible values, destroying all others. If not for the no cloning theorem, we could first measure ''f(x'') without measuring ''x, and then make a few copies of the resulting state (which is a superposition of states all having the same f''(''x)). Measuring x'' on these states would provide different ''x values which give the same f''(''x), leading to the period. Because we cannot make exact copies of a quantum state, this method does not work. Therefore, we have to carefully transform the superposition to another state that will return the correct answer with high probability. This is achieved by the quantum Fourier transform." "Note: another way to explain Shor's algorithm is by noting that it is just the quantum phase estimation algorithm in disguise." Category:Quantum Computing Category:Quantum Cryptography Category:Mathematics